# proevolytx@gmail.com
# 2012/12/17

# ======================================================================
# native functions of machine
# ======================================================================

class MHiPrint:
    def Str(s, obj):
        # print simple tags instead of the representing dict
        if type(obj[0]) == list:
            if obj[0][0] == "__inst__":
                return "<Instance Object>"
            elif obj[0][0] == "__class__":
                return "<Class Object>"
            elif obj[0][0] == "__method__":
                return "<Method Object>"
            elif obj[0][0] == "__func__":
                return "<Function Object>"
        return str(obj[0])
        
    def Run(s, mac, args):
        assert len(args) >= 1
        for arg in args[1:]:
            print s.Str(arg),
        if args[0][0]:
            print
        mac.stack.append([None])

# base class
# a.Run(args) means s.obj.Run(args)
# so method classes are created when subid instructions are executed
class MHiMethod:
    def __init__(s, obj):
        s.obj = obj

class MHiOr(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] or args[0][0]])

class MHiAnd(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] and args[0][0]])

class MHiAdd(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] + args[0][0]])

class MHiSub(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] - args[0][0]])

class MHiMul(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] * args[0][0]])

class MHiDiv(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] / args[0][0]])

class MHiMod(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] % args[0][0]])

class MHiLt(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] < args[0][0]])

class MHiGt(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] > args[0][0]])

class MHiLteq(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] <= args[0][0]])

class MHiGteq(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] >= args[0][0]])

class MHiEq(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] == args[0][0]])

class MHiNeq(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] != args[0][0]])

class MHiNeg(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 0
        mac.stack.append([-s.obj[0]])

class MHiPos(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 0
        mac.stack.append([+s.obj[0]])

class MHiNot(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 0
        mac.stack.append([not s.obj[0]])

class MHiIn(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] in args[0][0]])

class MHiNotIn(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] not in args[0][0]])

class MHiIs(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] is args[0][0]])

class MHiIsNot(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0] is not args[0][0]])

# INDEX, DELINDEX, SLICE, DELSLICE are used instead of
# __getitem__, __delitem__, __getslice__, __delslice__
# because a[None:None] is accepted while a.__getslice__(None, None) is not

class MHiIndex(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        mac.stack.append([s.obj[0][args[0][0]]])

class MHiDelIndex(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        del s.obj[0][args[0][0]]
        mac.stack.append([None])

class MHiSlice(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 2
        beg = args[0]
        end = args[1]
        mac.stack.append([s.obj[0][beg[0] : end[0]]])

class MHiDelSlice(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 2
        beg = args[0]
        end = args[1]
        del s.obj[0][beg[0] : end[0]]
        mac.stack.append([None])

class MHiInitAppend(MHiMethod):
    def Run(s, mac, args):
        assert len(args) == 1
        if type(s.obj[0]) == tuple:
            # the fake 'append' method of tuple
            s.obj[0] = s.obj[0] + (args[0][0], )
            mac.stack.append([None])
        elif type(s.obj) == list:
            s.obj[0].append(args[0][0])
            mac.stack.append([None])
        else:
            raise Exception("Init append only support lists and tuples.")

# ======================================================================
# machine
# ======================================================================

class MachineHi:
    def __init__(s):
        # global functions
        s.func = {}
        s.func["print"] = [MHiPrint()]

        # reserved global ids
        s.reserved = {
            "None" : None,
            "True" : True,
            "False" : False,
            "int" : int,
            "float" : float,
            "list" : list,
            "tuple" : tuple,
            "dict" : dict,
            "range" : range,
            "len" : len,
            "open" : open,
            "enumerate" : enumerate,
            "type" : type,
            "repr" : repr,
            "str" : str,
            "sorted" : sorted,
            "set" : set
            }

        s.Load([["halt"]])

    # load instructions to machine
    def Load(s, inst):
        s.inst = inst # intermediate instructions
        s.pc = 0 # instruction index
        s.stack = [] # main stack
        s.env = [{}] # domain stack for searching referenced ids
        s.pcstack = [] # pc stack for function calling
        s.ex = [] # exception stack
        s.imports = [] # python-runtime imports
        s.curclass = None # current class (for inclass)
        s.instcount = 0  # number of instructions execeuted
        
        s.label = {} # label->pc dict
        for linenum, instruction in enumerate(s.inst):
            if instruction[0] == "label":
                label = instruction[1]
                if label in s.label:
                    raise Exception("Duplicated label.")
                s.label[label] = linenum

    # simulate until user program finishes
    # debug:
    #   0: no debug
    #   1: print stack and current instruction after each step
    #   2: 1 and pause after each step
    def Simulate(s, debug):
        while True:
            warn = False
            if debug > 0 or warn:
                print "InstCount:", s.instcount, ":"
                print "PC:", s.pc, ":",
                for ins in s.inst[s.pc]:
                    print ins,
                print

            if not s.SimulateOneStepWithException():
                break

            if debug > 0 or warn:
                print "Stack:"
                for i in range(len(s.stack) - 1, -1, -1):
                    print s.stack[i]
                print
                if debug > 1:
                    raw_input()

    def SimulateOneStepWithException(s):
        try:
            ret = s.SimulateOneStep()
            return ret
        except Exception, e:
            # exception caught
            # goto the except code, and pop env and pcstacks
            if len(s.ex) > 0:
                ex = s.ex[-1]
                del s.ex[-1]
                s.pc = ex["pc"]
                s.env = s.env[:ex["envlen"]]
                s.pcstack = s.pcstack[:ex["pcstacklen"]]
                s.stack = s.stack[:ex["stacklen"]]
                s.stack.append([str(e)])
                return True
            else:
                raise Exception("Unhandled exception: " + str(e))

    def SimulateOneStep(s):
        if s.pc >= len(s.inst):
            raise Exception("PC overflowed.")
        
        s.instcount += 1
        inst = s.inst[s.pc]
        
        if inst[0] == "create":
            if inst[1] == "int":
                var = [int(inst[2])]
            elif inst[1] == "float":
                var = [float(inst[2])]
            elif inst[1] == "string":
                var = [str(inst[2])]
            elif inst[1] == "func":
                var = [["__func__", s.label[inst[2]]]]
            elif inst[1] == "method":
                var = [["__method__", s.label[inst[2]]]]
            elif inst[1] == "none":
                var = [None]
            elif inst[1] == "list":
                var = [[]]
            elif inst[1] == "tuple":
                var = [()]
            elif inst[1] == "dict":
                var = [{}]
            elif inst[1] == "class":
                var = [["__class__", {"__parent__" : inst[2]}]]
            else:
                raise Exception("Unknown constant type.")
            s.stack.append(var)
            
        elif inst[0] == "push":
            found = False

            # if in domain of class A
            # we try to push A.id first
            if s.curclass is not None:
                if inst[1] in s.curclass:
                    s.stack.append(s.curclass[inst[1]])
                    found = True

            # then we try to search id in domain stack (top to bottom)
            if not found:
                for i in range(len(s.env) - 1, -1, -1):
                    envslice = s.env[i]
                    if inst[1] in envslice:
                        s.stack.append(envslice[inst[1]])
                        found = True
                        break
                    
            # still not found
            if not found:
                # maybe id is a global registered function (print)
                if inst[1] in s.func:
                    s.stack.append(s.func[inst[1]])

                # reserved id (True, None, etc)
                elif inst[1] in s.reserved:
                    s.stack.append([s.reserved[inst[1]]])

                # still not found!!
                else:
                    # then maybe it is something in python-runtime
                    try:
                        for imp in s.imports:
                            if imp[1] is None:
                                exec("from " + imp[0] + " import *")
                            else:
                                exec("from " + imp[0] + " import " + imp[1])
                        s.stack.append([eval(inst[1])])
                    # ooops!
                    except Exception, e:
                        raise Exception("Cannot find name '" + inst[1] + "'.")
            
        elif inst[0] == "pop":
            if len(s.stack) == 0:
                raise Exception("Pop while stack is empty.")
            del s.stack[len(s.stack) - 1]
            
        elif inst[0] == "copytop":
            if len(s.stack) <= inst[1]:
                raise Exception("No enough elements in stack while copytop.")
            s.stack.append(s.stack[len(s.stack) - 1 - inst[1]])

        elif inst[0] == "newsubid":
            if len(s.stack) == 0:
                raise Exception("Try to create subid while stack is empty.")
            var = s.stack[-1]

            # create inst.subid
            if type(var[0]) == list and len(var[0]) == 2 and \
               var[0][0] in ["__class__", "__inst__"]:
                cls = var[0][1]
                cls[inst[1]] = [None]
            else:
                raise Exception("Invalid attribute operation.")
            
        elif inst[0] == "subid":
            if len(s.stack) == 0:
                raise Exception("Try to visit subid while stack is empty.")
            var = s.stack[-1]

            found = False

            # if current item is a user defined class or instance
            # try to find its subid
            if type(var[0]) == list and len(var[0]) == 2 and \
               var[0][0] in ["__class__", "__inst__"]:
                # find subid of a instance first
                if var[0][0] == "__inst__" and inst[1] in var[0][1]:
                    s.stack[-1] = var[0][1][inst[1]]
                    found = True

                # maybe its a subid of a class
                if not found:
                    cls = var[0][1]
                    if var[0][0] == "__inst__":
                        cls = var[0][1]["__class__"]

                    while True:
                        # print cls
                        if inst[1] in cls:
                            # bingo!
                            s.stack[-1] = cls[inst[1]]
                            top = s.stack[-1][0]
                            # if subid is a method of an instance
                            # then we should save the instance for
                            # the first argument when the method is called
                            if type(top) == list and len(top) == 2 and \
                               top[0] == "__method__" and \
                               var[0][0] == "__inst__":
                                top.append(var)
                            found = True
                            break
                        else:
                            # try to find subid in its parent class
                            if cls["__parent__"] is None:
                                break
                            cls = s.env[0][cls["__parent__"]["content"]][0][1]

            if found:
                pass
            # maybe it is some reserved subid
            elif inst[1] == "ADD":
                s.stack[-1] = [MHiAdd(var)]
            elif inst[1] == "SUB":
                s.stack[-1] = [MHiSub(var)]
            elif inst[1] == "MUL":
                s.stack[-1] = [MHiMul(var)]
            elif inst[1] == "DIV":
                s.stack[-1] = [MHiDiv(var)]
            elif inst[1] == "OR":
                s.stack[-1] = [MHiOr(var)]
            elif inst[1] == "AND":
                s.stack[-1] = [MHiAnd(var)]
            elif inst[1] == "LT":
                s.stack[-1] = [MHiLt(var)]
            elif inst[1] == "GT":
                s.stack[-1] = [MHiGt(var)]
            elif inst[1] == "LTEQ":
                s.stack[-1] = [MHiLteq(var)]
            elif inst[1] == "GTEQ":
                s.stack[-1] = [MHiGteq(var)]
            elif inst[1] == "EQ":
                s.stack[-1] = [MHiEq(var)]
            elif inst[1] == "NEQ":
                s.stack[-1] = [MHiNeq(var)]
            elif inst[1] == "MOD":
                s.staack[-1] = [MHiMod(var)]
            elif inst[1] == "NEG":
                s.stack[-1] = [MHiNeg(var)]
            elif inst[1] == "POS":
                s.stack[-1] = [MHiPos(var)]
            elif inst[1] == "NOT":
                s.stack[-1] = [MHiNot(var)]
            elif inst[1] == "IN":
                s.stack[-1] = [MHiIn(var)]
            elif inst[1] == "NOTIN":
                s.stack[-1] = [MHiNotIn(var)]
            elif inst[1] == "IS":
                s.stack[-1] = [MHiIs(var)]
            elif inst[1] == "ISNOT":
                s.stack[-1] = [MHiIsNot(var)]
            elif inst[1] == "INIT_APPEND":
                s.stack[-1] = [MHiInitAppend(var)]
            elif inst[1] == "INDEX":
                s.stack[-1] = [MHiIndex(var)]
            elif inst[1] == "SLICE":
                s.stack[-1] = [MHiSlice(var)]
            elif inst[1] == "DELINDEX":
                s.stack[-1] = [MHiDelIndex(var)]
            elif inst[1] == "DELSLICE":
                s.stack[-1] = [MHiDelSlice(var)]
            else:
                # still not found!
                # maybe its is a subid of a python-runtime class
                try:
                    s.stack[-1] = [var[0].__getattribute__(inst[1])]
                except Exception, e:
                    # for some other strange classes
                    try:
                        s.stack[-1] = [var[0].__getattr__(inst[1])]
                    except Exception, e:
                        # print s.stack[-1], s.instcount, s.pc
                        raise Exception("Unfound attribute '"+ inst[1] +"'.")
            
        elif inst[0] == "call":
            if len(s.stack) < 2:
                raise Exception("Try to call function while there is no " +
                                "enough elements in stack to assign.")
            func = s.stack[-1][0]
            #print func

            # reserved functions
            if func in [bool, int, float, list, tuple, dict, set,
                        range, sorted, enumerate,
                        len, str, repr, type, open]:
                del s.stack[-1]
                argc = s.stack[-1][0]
                del s.stack[-1]
                
                if argc == 0:
                    s.stack.append([func()])
                    
                elif argc == 1:
                    var = s.stack[-1][0]
                    del s.stack[-1]
                    s.stack.append([func(var)])
                    
                elif argc == 2 and func in [open, range]:
                    arg1 = s.stack[-1][0]
                    del s.stack[-1]
                    arg2 = s.stack[-1][0]
                    del s.stack[-1]
                    s.stack.append([func(arg1, arg2)])
                    
                elif argc == 3 and func == range:
                    arg1 = s.stack[-1][0]
                    del s.stack[-1]
                    arg2 = s.stack[-1][0]
                    del s.stack[-1]
                    arg3 = s.stack[-1][0]
                    del s.stack[-1]
                    s.stack.append([func(arg1, arg2, arg3)])
                    
                else:
                    print func
                    raise Exception("Too many arguments.")

            # user defined functions
            elif type(func) is list and len(func) >= 2 and \
                 func[0] in ["__func__", "__method__"]:
                del s.stack[-1]

                # if it is a method called by a instance
                # we should push the instance into the stack first
                if func[0] == "__method__" and len(func) == 3:
                    argc = s.stack[-1]
                    del s.stack[-1]
                    s.stack.append(func[2])
                    del func[2]
                    s.stack.append([argc[0] + 1])
                    
                s.pcstack.append([s.pc + 1, len(s.ex)])
                s.pc = func[1]
                s.env.append({})
                return True

            # class constructions by calling ClassName()
            elif type(func) is list and len(func) == 2 and \
                 func[0] == "__class__":
                del s.stack[-1]
                argc = s.stack[-1]
                del s.stack[-1]

                # we try to find the __init__ function of the class
                init = None
                cls = func[1]
                while True:
                    if "__init__" in cls:
                        init = cls["__init__"]
                        break
                    if cls["__parent__"] is None:
                        break
                    # try to find it in its parent class
                    cls = s.env[0][cls["__parent__"]["content"]][0][1]

                if init is not None:
                    # if we found __init__ function
                    # we create a instance of the class
                    # then call __init__ with it
                    # __init__ functions will automatically
                    # return the created class
                    s.stack.append([["__inst__", {"__class__" : func[1]}]])
                    s.stack.append([argc[0] + 1])
                    s.pcstack.append([s.pc + 1, len(s.ex)])
                    s.pc = init[0][1]
                    s.env.append({})
                    return True
                else:
                    # no __init__ functions are found
                    # delete the arguments and create a empty instance
                    for i in range(argc[0]):
                        del s.stack[-1]
                    s.stack.append([["__inst__", {"__class__" : func[1]}]])

            # python-runtion function or method
            # seem to be the same of the first case...
            elif str(type(func)) in [
                "<type 'method-wrapper'>",
                "<type 'builtin_function_or_method'>",
                "<type 'function'>",
                "<type 'classobj'>"]:
                del s.stack[-1]
                argc = s.stack[-1][0]
                del s.stack[-1]
                if len(s.stack) < argc:
                    raise Exception("No enough arguments in stack.")
                args = []
                for i in range(argc):
                    args.append(s.stack[-1])
                    del s.stack[-1]

                # we do not support syntax like:
                # s.stack.append([func(*args)])
                # so we use the ugly one:
                if len(args) == 0:
                    s.stack.append([func()])
                elif len(args) == 1:
                    s.stack.append([func(args[0][0])])
                elif len(args) == 2:
                    s.stack.append([func(args[0][0], args[1][0])])
                elif len(args) == 3:
                    s.stack.append([func(args[0][0], args[1][0],
                                         args[2][0])])
                elif len(args) == 4:
                    s.stack.append([func(args[0][0], args[1][0],
                                         args[2][0], args[3][0])])
                else:
                    raise Exception("Too much arguments.")

            # finally, try native functions
            else:
                del s.stack[-1]
                argc = s.stack[-1][0]
                del s.stack[-1]
                if len(s.stack) < argc:
                    print func
                    print "argc", argc
                    print "stack", s.stack
                    print "insts", s.instcount
                    raise Exception("No enough arguments in stack.")
                args = []
                for i in range(argc):
                    args.append(s.stack[-1])
                    del s.stack[-1]
                func.Run(s, args)
            
        elif inst[0] == "newid":
            if s.curclass is None:
                s.env[-1][inst[1]] = [None]
            else:
                s.curclass[inst[1]] = [None]
            
        elif inst[0] == "assign":
            if len(s.stack) < 2:
                raise Exception("No enough elements in stack to assign.")
            s.stack[-1][0] = s.stack[-2][0]
            
        elif inst[0] == "halt":
            # all the stacks should be clean when halt is executed
            if len(s.stack) != 0 or len(s.ex) != 0 or \
               len(s.pcstack) != 0 or len(s.env) != 1:
                raise Exception("Machine halts, but stack is not empty." + \
                                "ex = " + len(s.ex))
            return False

        elif inst[0] == "label":
            pass

        elif inst[0] == "goto":
            if inst[1] not in s.label:
                raise Exception("Label not exist.")
            s.pc = s.label[inst[1]]
            return True

        elif inst[0] == "ifnot":
            if len(s.stack) == 0:
                raise Exception("Stack is empty.")
            top = s.stack[-1][0]
            del s.stack[-1]
            if not top:
                if inst[1] not in s.label:
                    raise Exception("Label not exist.")
                s.pc = s.label[inst[1]]
                return True

        elif inst[0] == "ret":
            if len(s.env) <= 1:
                raise Exception("Env stack underflow.")
            del s.env[-1]
            if len(s.pcstack) == 0:
                raise Exception("Return not in function body.")
            s.pc = s.pcstack[-1][0]
            # may jump out some try-bodies
            s.ex = s.ex[:s.pcstack[-1][1]]
            del s.pcstack[-1]
            return True

        # similar to but much simpler than newid
        elif inst[0] == "delid":
            found = False
            
            if s.curclass is not None:
                if inst[1] in s.curclass:
                    del s.curclass[inst[1]]
                    found = True
                    
            if not found:
                for i in range(len(s.env) - 1, -1, -1):
                    envslice = s.env[i]
                    if inst[1] in envslice:
                        del envslice[inst[1]]
                        found = True
                        break
                    
            if not found:
                raise Exception("'" + inst[1] + "' is reserved or not exsit.")

        # explicitly raise an exception
        elif inst[0] == "raise":
            if len(s.stack) > 0:
                ex = s.stack[-1][0]
                del s.stack[-1]
            else:
                ex = "Empty exception. (FATAL)"
            raise Exception(ex)

        # push the exception stack
        elif inst[0] == "pushex":
            s.ex.append({"pc" : s.label[inst[1]],
                         "envlen" : len(s.env),
                         "pcstacklen" : len(s.pcstack),
                         "stacklen" : len(s.stack)})
            #print len(s.ex), s.instcount

        # pop the exception stack
        elif inst[0] == "popex":
            if len(s.ex) == 0:
                raise Exception("Exception stack underflow.")
            del s.ex[-1]

        # change the domain to a class
        elif inst[0] == "inclass":
            if s.curclass is not None:
                raise Exception("Already in class.")
            if inst[1] in s.env[0]:
                s.curclass = s.env[0][inst[1]][0][1]
            else:
                raise Exception("Unknown class.")

        # change the domain to global
        elif inst[0] == "outclass":
            if s.curclass is None:
                raise Exception("Already out of class.")
            s.curclass = None

        # import system libs
        elif inst[0] == "import":
            s.imports.append(inst[1:])

        else:
            raise Exception("Unknown instruction '" + inst[0] + "'.")

        s.pc += 1
        return True
